import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class TrieTree {
	
	//根节点
	private Node root;
	//重写一个比较器
	private Comparator<Map.Entry<String, Integer>> comparator;
	protected class Node {
		protected int words;
		protected int prefixes;
		protected Node[] edges;		//每个节点包含26个子节点 包括一个空节点
		
		Node()
		{
			words = 0;
			prefixes = 0;
			edges = new Node[27];
			//初始化子节点
			for (int i = 0; i < edges.length; i++) {
				edges[i] = null;
			}
		}
	}
	
	public TrieTree()
	{
		root = new Node();
		//比较器实现
		comparator = new Comparator<Map.Entry<String, Integer>>() {
			public int compare(Map.Entry<String, Integer> obj1,Map.Entry<String, Integer> obj2) {
				return obj2.getValue() - obj1.getValue();
			}
		};
	}
	
	//插入单词
	public void insertWord(String word)
	{
		this.insertWord(root, word);
	}
	public void insertWord(Node node, String word)
	{
		if(word.length() == 0){
			node.words++;
		}else{
			node.prefixes++;
			char c = word.charAt(0);
			c = Character.toLowerCase(c);
			int index = c - 'a';
			if(node.edges[index] == null){
				node.edges[index] = new Node();
			}
			//递归
			insertWord(node.edges[index], word.substring(1));
		}
	}
	//所有单词
	public List<String> listAllWords()
	{
		List<String> list = new ArrayList<String>();
		Node[] edges = root.edges;
		for (int i = 0; i < edges.length; i++) {
			if(edges[i] != null){
				String word = "" + (char) ('a' + i);
				depthFirstSearch(list, edges[i], word);
			}
			
		}
		return list;
	}
	
	//深度优先搜索
	public void depthFirstSearch(List<String> words, Node node, String word)
	{
		Node[] edges = node.edges;
		boolean hasChildren = false;
		for(int i=0; i<edges.length; i++){
			if(edges[i] != null){
				hasChildren = true;
				String tempWord = word + (char)('a' + i);
				depthFirstSearch(words, edges[i], tempWord);
			}
		}
		if(!hasChildren){
			words.add(word);
		}
	}
	
	//统计词频
	public int countWords(String word)
	{
		return countWords(root, word);
	}
	
	public int countWords(Node node, String word)
	{
		if(word.length() == 0){
			return node.words;
		}else{
			char c = word.charAt(0);
			int index = c - 'a';
			if(node.edges[index] == null){
				return 0;
			}else{
				return countWords(node.edges[index], word.substring(1));
			}
		}
	}
	
	//获取Top10里面的最小值
	public Entry<String, Integer> getMinTopValue(Map<String, Integer> topK)
	{
		//将TreeMap转换成list
		List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(topK.entrySet());
		//排序
		Collections.sort(list,comparator);
		return list.get(list.size()-1);
	}
	
	//打印前10个
	public void printTop10()
	{
		Map<String, Integer> topK = new TreeMap<String, Integer>();
		List<String> list = this.listAllWords();
		Iterator<String> it = list.iterator();
		int i = 0;
		while(it.hasNext()){
			String temp = it.next();
			int count = countWords(temp);
			//初始化存储10个单词
			if(i < 10){
				topK.put(temp, count);
			}else{
				if(this.getMinTopValue(topK).getValue() < count){
					//移除
					topK.remove(this.getMinTopValue(topK).getKey());
					//加入新的单词
					topK.put(temp, count);
				}
			}
			i++;
		}
		//将TreeMap转换成list
		List<Map.Entry<String, Integer>> topList = new ArrayList<Map.Entry<String, Integer>>(topK.entrySet());
		//排序
		Collections.sort(topList,comparator);
		//打印
		for(int j = 0;j<topList.size();j++){
			String key = topList.get(j).getKey();
			Integer value = topList.get(j).getValue();
			System.out.print("Top "+(j+1)+" : ");
			System.out.println(key + " " + value);
		}
	}
}